package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @see <a href=https://leetcode.cn/problems/binary-tree-right-side-view/>二叉树的右视图</a>
 *
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，
 * 按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 */
public class RightSideView199 {
    public static List<Integer> rightSideView(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        Queue<RightSideViewHelp> queue = new ArrayBlockingQueue<>(65535);
        queue.add(new RightSideViewHelp(0, root));
        Map<Integer, Boolean> xx = new HashMap<>();

        while (!queue.isEmpty()) {
            RightSideViewHelp curHelp = queue.poll();
            Integer cen = curHelp.getCen();
            TreeNode cur = curHelp.getTreeNode();

            if (xx.get(cen) == null || !xx.get(cen)) {
                res.add(cur.val);
                xx.put(cen, true);
            }

            TreeNode right = cur.right;
            TreeNode left = cur.left;

            if (right != null) {
                queue.add(new RightSideViewHelp(cen + 1, right));
            }
            if (left != null) {
                queue.add(new RightSideViewHelp(cen + 1, left));
            }
        }
        return res;
    }

    static class RightSideViewHelp {
        private Integer cen;
        private TreeNode treeNode;

        public RightSideViewHelp() {
        }

        public RightSideViewHelp(Integer cen, TreeNode treeNode) {
            this.cen = cen;
            this.treeNode = treeNode;
        }

        public Integer getCen() {
            return cen;
        }

        public void setCen(Integer cen) {
            this.cen = cen;
        }

        public TreeNode getTreeNode() {
            return treeNode;
        }

        public void setTreeNode(TreeNode treeNode) {
            this.treeNode = treeNode;
        }
    }

    public static void main(String[] args) {
        TreeNode o = TreeNode.generatorTreeNode(new Integer[] {1,2,3,4});

        List<Integer> integers = rightSideView(o);

        System.err.println("OK");
    }
}
